package com.example.array.doublepointer;

/**
 * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
 * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 */
public class Leetcode26_RemoveDuplicates {
    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 2, 3, 4};
        System.out.println(new Solution().removeDuplicates(nums));
        for (int num : nums) {
            System.out.println(num);
        }

    }

    static class Solution {

        /**
         * 双指针法二:
         * 因为给定数组是有序的，所以相同元素必然连续,当数组 nums 的长度大于 0时，数组中至少包含一个元素，在删除重复元素之后也至少剩下一个元素，
         *
         * 因此 nums[0]保持原状即可，从下标 1 开始删除重复元素。
         * 定义两个指针 slow 和 fast 分别为慢指针和快指针，其中慢指针表示处理出的数组的长度，快指针表示已经检查过的数组的长度
         * 初始化slow和fast都为1
         * 要求相同元素最多出现一次，所以我们需要检查上个被检查过的的元素 nums[fast - 1] 是否和当前待检查元素 nums[fast] 相同。
         * 当 nums[fast−1] != nums[fast] 时，说明 nums[fast] 和之前的元素都不同，因此将 nums[fast] 的值复制到 nums[slow]，
         * 然后将 slow 的值加 1，即指向下一个位置。
         *
         * 最后，slow 即为处理好的数组的长度。
         *
         * @param nums
         * @return
         */
        private int removeDuplicates3(int[] nums) {
            if (nums == null) return 0;
            // 数组的第一个数必然可以被保留，因此对于长度不超过 1 的数组，直接返回即可
            if (nums.length <= 1) return nums.length;

            int slow = 1, fast = 1;
            while (fast < nums.length) {
                if (nums[fast] != nums[fast - 1]) {
                    nums[slow++] = nums[fast];
                }

                ++fast;
            }
            return slow;

        }

        /**
         * 最优解:双指针法
         * <p>
         * 1.定义两个指针（索引）分别指向目标位和待移动元素位
         * 初始目标位为0，待移动元素位为1
         * 2.比较两个指针对应的数据
         * 比较相等：目标位不变，待移动位加1
         * 比较不等：目标位加1，待移动元素赋值到目标位；待移动位加1
         * <p>
         * 边界问题
         * 只需要一层循环，循环退出条件：待移动指针超出数组范围
         * 细节问题
         * 题目要求返回数组新长度，即目标位对应的数据是最后一个元素，下标+1
         * 尝试移动元素前，若目标位与待移动位相同，跳过赋值操作
         *
         * @param nums
         * @return
         */
        private int removeDuplicates2(int[] nums) {
            if (nums == null) {
                return 0;
            }
            int target = 0, waitMove = 1; // 定义两个指针分别代表目标位和待移动位

            for (; waitMove < nums.length; waitMove++) {
                if (nums[target] != nums[waitMove]) {
                    if (++target != waitMove) {
                        nums[target] = nums[waitMove];
                    }
                }
            }
            return ++target;
        }

        /**
         * 暴力法
         * 遍历数组，比较相邻两个元素，如果相同就将数组后面的所有元素向前移动一位
         *
         * @param nums
         * @return
         */
        private int removeDuplicates1(int[] nums) {
            if (nums == null) {
                return 0;
            }
            int numslen = nums.length;
            for (int i = 0; i < numslen - 1; ) {
                if (nums[i] != nums[i + 1]) { // 只有当相邻元素不相等时，索引才需要+1
                    i++;
                } else {
                    for (int j = i + 1; j < numslen - 1; j++) {
                        nums[j] = nums[j + 1];
                    }
                    // 只要数组后面的元素向前移动过一位则说明有一个重复的项
                    numslen--;
                }
            }
            return numslen;
        }


        public int removeDuplicates(int[] nums) {
            return removeDuplicates3(nums);
        }
    }

}
